package BackTrackingPackage;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class combine_ {
  /*list为单个符合要求的集合*/
  LinkedList<Integer> list = new LinkedList<>();
  /*result为整体结果集合*/
  List<List<Integer>> result = new ArrayList<>();
  /*
  * 回溯三部曲:
  * 1. 确定返回值类型和参数
  * 2. 确定终止条件
  * 3. 确定每层递归的逻辑
  */
  /*public  void backTracking(int n,int k,int startIndex){
      *//*判断终止条件*//*
    if (list.size() == k){
      result.add(new ArrayList<>(list));
      return;
    }
    *//*确定每层的处理逻辑*//*
    for (int i = startIndex ; i < n ; i++){
      list.add(i);
      *//*从原来的 1 2 3 4 挑一个 变成了 2 3 4挑一个 是同样的问题, 只不过是问题规模变小了*//*
      backTracking(n,k,i + 1);
      *//*回溯, 将符合要求的集合的最后一个元素弹出*//*
      list.removeLast();
    }
  }*/

  /*回溯算法的返回值一般是void
  * 参数是n,k 都是题目给的
  * startIndex是标志, 每次选元素时应该从哪个元素开始选
  * 加入集合[1,2,3,4]中, 第一次选 startIndex=1;
  * 选到了 1 那还剩[2,3,4]三个元素可以选, 则start = 2, 意思就是下次选择元素
  * 从 2开始选
  * */
  public void backTracking(int n,int k, int startIndex){
    /*判断递归的终止条件*/
    /*终止条件就是 list集合的长度为k*/
    if (list.size() == k){
      /*将list加入到result中*/
      result.add(new ArrayList<>(list));
      return;
    }
    /*循环*/
    /*这里存在循环是因为, 选完1之后, 还有[2,3,4]三个元素可以进行组合, 所以有三种选择*/
    /*假如这次选1, 之后还可以选[2,3,4]应该有三次循环*/
    for (int i = startIndex ; i <= n - (k - list.size()) + 1 ; i++){
      /*先将选到的1加入到list中*/
      list.add(i);
      /*现在选到1了, 下面继续进行选择, 又成了一开始的问题了, 但是问题规模从一开始的[1,2,3,4]选一个变成了[2,3,4]选一个*/
      backTracking(n,k,i + 1);
      /*回溯, 若此时第二次递归选到了2, 即list = [1,2]
      * 那此时就需要进行回溯, 即将2弹出, 以便下次取3, 组成list=[1,3];
      * */
      list.removeLast();
    }
  }
}

